#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "xcommon.h"

#include "llist.h"

#include "xmalloc.h"    // for xcalloc and xfree

LLIST *ll_new_el(void *data) {
// Returns a new element
    LLIST *tmp=(LLIST *)xcalloc(1, sizeof(LLIST));
    tmp->data=data;
    return tmp;
}

LLIST *ll_append_el(LLIST **el, void *data) {
// Append an element to the list; if the list is a loop, the element is added after the element given to the function
    if(!el) return NULL;
    LLIST *last=ll_get_last_el(*el);
    if(last) {
        LLIST *tmp=last->next; // in case of loop
        last->next=ll_new_el(data);
        last->next->prev=last;
        last->next->next=tmp;
        if(tmp) tmp->prev=last->next;  // in case of loop

        return last->next;
    }
    else return (*el=ll_new_el(data));
}

bool ll_is_loop(LLIST *el) {
// Returns true if the list is a loop
    LLIST *in=el;
    while(el) {
        el=el->next;
        if(el==in) return true; // in case of loop
    }
    return false;
}

LLIST *ll_get_first_el(LLIST *el) {
// Returns the first element of the list; if the list is a loop, it returns the input element
    if(!el) return NULL;
    LLIST *in=el;
    while(el->prev) {
        el=el->prev;
        if(el==in) break;   // in case of loop
    }
    return el;
}

LLIST *ll_get_nth_el(LLIST *el, u32 num) {
// Returns the num-th element of the list (deprecated, can be slow with a far element)
    if(!num) return NULL;
    u32 i=1;
    el=ll_get_first_el(el);
    while(el && num>i) {
        i++;
        el=el->next;
    }
    return el;
}

LLIST *ll_get_last_el(LLIST *el) {
// Returns the last element of the list; if the list is a loop, it returns the input element
    if(!el) return NULL;
    LLIST *in=el;
    while(el->next) {
        el=el->next;
        if(el==in) break;   // in case of loop
    }
    return el;
}

u32 ll_get_num_el(LLIST *el) {
// Returns the number of elements in the linked list
    u32 count=0;
    LLIST *in=el=ll_get_first_el(el);
    while(el) {
        count++;
        el=el->next;
        if(el==in) break;   // in case of loop
    }
    return count;
}

void ll_for_each_data(LLIST *el, datahandler llh) {
// Call the handler for each element in the list
    LLIST *in=el=ll_get_first_el(el);
    if(!el || !llh) return;
    while(el) {
        llh(el->data);
        el=el->next;
        if(el==in) break;   // in case of loop
    }
    return;
}

LLIST *ll_search_data(LLIST *el, void *data) {
// Search a pointer in the elements of a list
    if(!el) return NULL;
    LLIST *in=el;
    while(el) { // search first in the elements after the input one
        if(el->data==data) return el;
        el=el->next;
        if(el==in) return NULL; // in case of loop
    }
    el=in->prev;
    while(el) { // search now in the elements before the input one
        if(el->data==data) return el;
        el=el->prev;
    }
    return NULL;
}

void ll_sort(LLIST *el, datacmp llc) {
// Sort the list, the input element will be the first of the list (this is a custom insertion sort)
    LLIST *in=el;
    el=ll_get_first_el(el);
    if(!el || ll_is_loop(el) || !llc) return;

    LLIST *lli, *llj, *nj, *tmp;
    for(llj=el->next; llj; ) {
        for(lli=llj; lli->prev && llc(llj->data, lli->prev->data)<=0; lli=lli->prev);

        nj=llj->next;
        if(lli!=llj) {
            llj->prev->next=llj->next;
            if(lli->prev) lli->prev->next=llj;
            tmp=llj->prev;
            llj->prev=lli->prev;
            lli->prev=llj;
            if(llj->next) llj->next->prev=tmp;
            llj->next=lli;
        }
        llj=nj;
    }

    tmp=ll_get_first_el(el);
    if(tmp!=in) {   // invert the elements in and tmp
        LLIST tp;
        memcpy(&tp, tmp, sizeof(LLIST));
        memcpy(tmp, in, sizeof(LLIST));
        memcpy(in, &tp, sizeof(LLIST));
        if(in->next==in) {
            in->next=tmp;
            tmp->prev=in;
        }
        else {
            in->next->prev=in;
            tmp->prev->next=tmp;
        }
        if(tmp->next) tmp->next->prev=tmp;
    }    // in point now to the first element
}

void ll_free_el(LLIST *el) {
// Free an element, linking the two elements around if necessary
    if(!el) return;

    if(el->next && el->prev) {
        el->prev->next=el->next;
        el->next->prev=el->prev;
    }
    else if(el->prev) el->prev->next=NULL;
    else if(el->next) el->next->prev=NULL;

    bzero((void *)el, sizeof(LLIST));
    xfree(el);
}

void ll_free_all(LLIST *el) {
// Delete all the list
    el=ll_get_first_el(el);
    if(!el) return;

    LLIST *tmp;
    while(el) {
        tmp=(el==el->next)?NULL:el->next;

        ll_free_el(el);

        el=tmp;
    }
}

void ll_free_all_handler(LLIST *el, datahandler llh) {
// Delete all the list and give each element to a user handler, so he can free himself his allocated memory in the data field
    el=ll_get_first_el(el);
    if(!el) return;

    LLIST *tmp;
    while(el) {
        tmp=(el==el->next)?NULL:el->next;

        if(llh && el->data) llh(el->data);
        ll_free_el(el);

        el=tmp;
    }
}

